P(w Teilwort von v), |w| < |v| < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
Seien [mm] \Sigma [/mm] und [mm] \tilde{\Sigma} [/mm] zwei Alphabete, [mm] \tilde{\Sigma} \subseteq \Sigma. [/mm] Seien weiter m, n [mm] \in \mathds{N} [/mm] mit m < n und v [mm] \in \tilde{\Sigma}^{m}, [/mm] w [mm] \in \Sigma^{n}. [/mm] Wie hoch ist die Wahrscheinlichkeit bei gleichverteilter Ziehung von v und w, dass v ein Teilwort von w ist? Wie muss v gewählt werden, dass die Wahrscheinlichkeit möglichst gering wird? (insbesondere, wenn m > [mm] |\tilde{\Sigma}|)
[/mm]
v ist gdw. ein Teilwort von w, wenn es ein p [mm] \in [/mm] {0, ..., |w|-|v|} gibt, sodass v(i) = w(p+i) für alle i [mm] \in [/mm] {0, ..., |v|-1}.
Trotzdem dieses Problem scheinbar einfach aussieht, verzweifele ich gerade daran: Wie kann ich berechnen, wie viele Wörter aus [mm] \Sigma^{n} [/mm] ein gegebenes Wort als Teilwort enthalten? Interessanterweise enthält die Sprache [mm] \{ A, ..., Z\}^5 [/mm] genau 2028 verschiedene Wörter, die "AAB" als Teilwort enthalten, allerdings nur 2027 versch. Wörter die "ABA" enthalten und nur 1976 Wörter, die "AAA" enthalten. (Die Werte habe ich durch Aufzählen aller Wörter mithilfe eines Programmes ermittelt)
Hat jemand eine Idee?
Vielen Dank im Voraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:21 Do 02.07.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
